/*  Copyright (c) 2012 Xiaoyun Zhu
 * 
 *  Permission is hereby granted, free of charge, to any person obtaining a copy  
 *  of this software and associated documentation files (the "Software"), to deal  
 *  in the Software without restriction, including without limitation the rights  
 *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell  
 *  copies of the Software, and to permit persons to whom the Software is  
 *  furnished to do so, subject to the following conditions:
 *  
 *  The above copyright notice and this permission notice shall be included in  
 *  all copies or substantial portions of the Software.
 *  
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR  
 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  
 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE  
 *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER  
 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,  
 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN  
 *  THE SOFTWARE.  
 */
package cn.kk.fluidcells;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.ServiceLoader;
import java.util.Set;

import cn.kk.fluidcells.api.CellIdentifier;
import cn.kk.fluidcells.api.CellPlugin;

public class CellPluginService {
    private static CellPluginService pluginService;

    private final ServiceLoader<CellPlugin> serviceLoader;

    private CellPluginService() {
        // load all the classes in the classpath that have implemented the interface
        this.serviceLoader = ServiceLoader.load(CellPlugin.class);
    }

    public static CellPluginService getInstance() {
        if (CellPluginService.pluginService == null) {
            CellPluginService.pluginService = new CellPluginService();
        }
        return CellPluginService.pluginService;
    }

    public List<CellPlugin> getOrderedPlugins() {
        List<CellPlugin> cellPlugins = new LinkedList<CellPlugin>();
        Iterator<CellPlugin> iterator = this.serviceLoader.iterator();
        while (iterator.hasNext()) {
            cellPlugins.add(iterator.next());
        }
        return orderPluginsByDependencies(cellPlugins);
    }

    private static final class CellPluginEdge {
        public final CellPluginNode from;

        public final CellPluginNode to;

        public CellPluginEdge(CellPluginNode from, CellPluginNode to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object obj) {
            CellPluginEdge e = (CellPluginEdge) obj;
            return e.from.equals(this.from) && e.to.equals(this.to);
        }
    }

    private static final class CellPluginNode {
        public final CellIdentifier id;

        public final HashSet<CellPluginEdge> inEdges;

        public final HashSet<CellPluginEdge> outEdges;

        public CellPluginNode(CellIdentifier plugin) {
            this.id = plugin;
            this.inEdges = new HashSet<CellPluginEdge>();
            this.outEdges = new HashSet<CellPluginEdge>();
        }

        public CellPluginNode addEdge(CellPluginNode node) {
            CellPluginEdge e = new CellPluginEdge(this, node);
            this.outEdges.add(e);
            node.inEdges.add(e);
            return this;
        }

        @Override
        public boolean equals(Object obj) {
            CellPluginNode o = (CellPluginNode) obj;
            return o.id.equals(this.id);
        }
    }

    protected List<CellPlugin> orderPluginsByDependencies(List<CellPlugin> cellPlugins) {
        List<CellPlugin> uniques = new LinkedList<CellPlugin>();
        for (CellPlugin p : cellPlugins) {
            addNewestPlugin(uniques, p);
        }

        List<CellPlugin> ordered = orderUniqueCellPlugins(uniques);
        return ordered;
    }

    private List<CellPlugin> orderUniqueCellPlugins(List<CellPlugin> uniques) {
        List<CellPlugin> ordered = new LinkedList<CellPlugin>();
        List<CellPluginNode> nodes = createCellPluginNodes(uniques);

        Set<CellPluginNode> independentSet = new HashSet<CellPluginNode>();
        for (CellPluginNode n : nodes) {
            if (n.inEdges.isEmpty()) {
                independentSet.add(n);
            }
        }
        while (!independentSet.isEmpty()) {
            CellPluginNode n = independentSet.iterator().next();
            independentSet.remove(n);
            ordered.add(getCellPlugin(uniques, n.id));

            for (Iterator<CellPluginEdge> it = n.outEdges.iterator(); it.hasNext();) {
                CellPluginEdge e = it.next();
                CellPluginNode m = e.to;
                it.remove();
                m.inEdges.remove(e);

                if (m.inEdges.isEmpty()) {
                    independentSet.add(m);
                }
            }
        }
        for (CellPluginNode n : nodes) {
            if (!n.inEdges.isEmpty()) {
                System.err.println("Cyclic dependencies found: " + n.id);
                break;
            }
        }
        return ordered;
    }

    /**
     * @param uniques
     * @return
     */
    private List<CellPluginNode> createCellPluginNodes(List<CellPlugin> uniques) {
        Map<CellIdentifier, CellPluginNode> nodesMap = new HashMap<CellIdentifier, CellPluginNode>();
        for (CellPlugin u : uniques) {
            nodesMap.put(u.getIdentifier(), new CellPluginNode(u.getIdentifier()));
        }

        List<CellPluginNode> nodes = new LinkedList<CellPluginNode>();
        for (CellPlugin u : uniques) {
            boolean depOkay = true;
            CellPluginNode node = nodesMap.get(u.getIdentifier());
            final List<CellIdentifier> dep = u.getDependencies();
            for (CellIdentifier i : dep) {
                CellPluginNode d = nodesMap.get(i);
                if (d != null) {
                    d.addEdge(node);
                } else {
                    System.err.println("Dependency " + i + " not found for plugin " + u);
                    depOkay = false;
                    break;
                }
            }
            if (depOkay) {
                nodes.add(node);
            }
        }
        return nodes;
    }

    private CellPlugin getCellPlugin(List<CellPlugin> plugins, CellIdentifier i) {
        for (CellPlugin p : plugins) {
            if (p.getIdentifier().isCompatibleWith(i)) {
                return p;
            }
        }
        return null;
    }

    /**
     * @param ordered
     * @param p
     */
    private void addNewestPlugin(List<CellPlugin> ordered, CellPlugin p) {
        // check for same plugins and replace it if newer
        CellPlugin same = null;
        CellIdentifier pid = p.getIdentifier();
        for (CellPlugin o : ordered) {
            if (o.getIdentifier().isSame(pid)) {
                same = o;
                break;
            }
        }
        if (same != null) {
            if (pid.isNewerThan(same.getIdentifier())) {
                ordered.remove(same);
                ordered.add(p);
            }
        } else {
            ordered.add(p);
        }
    }

    public List<CellPlugin> initCells() {
        List<CellPlugin> plugins = getOrderedPlugins();
        for (CellPlugin p : plugins) {
            p.init();
        }
        return plugins;
    }
}
